package backTrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 488. 祖玛游戏
 */
public class P488 {
    private Map<Character, Integer> itemMap = null;

    public int findMinStep(String board, String hand) {
        // 1. 初始化map
        itemMap = new HashMap<>();
        for (char c : hand.toCharArray()) {
            if (!itemMap.containsKey(c)) {
                itemMap.put(c, 0);
            }
            itemMap.put(c, itemMap.get(c) + 1);
        }
        // 2. 执行回溯
        List<Integer> totalList = new ArrayList<>();
        backTrack(board, 0, hand.length(), totalList);
        if (totalList.size() == 0) {
            return -1;
        } else {
            return totalList.stream().mapToInt(b -> b).min().getAsInt();
        }
    }

    private void backTrack(String sequence, Integer usedCount, Integer totalBall, List<Integer> totalList) {
        // 消除满足要求的球
        sequence = sweep(sequence);
        if (sequence.length() == 0) {// 消解完成
            totalList.add(usedCount);
            return;
        } else if (usedCount == totalBall) {//无法消解
            return;
        } else {
            List<Integer> suitPos = getSuitPos(sequence, itemMap);
            for (int pos : suitPos) {
                int tmp = pos;
                int existCount = 0;
                // 1. 找到存在的数量
                char c = sequence.charAt(tmp);
                while (tmp < sequence.length() && sequence.charAt(tmp++) == c) {
                    existCount++;
                }
                // 2. 弹入
                itemMap.put(c, itemMap.get(c) - (3 - existCount));
                StringBuilder sb = new StringBuilder();
                sb.append(sequence.substring(0, pos));
                for (int i = 0; i < 3 - existCount; i++) {
                    sb.append(c);
                }
                sb.append(sequence.substring(pos, sequence.length()));
                usedCount += 3 - existCount;
                // 3. 执行回溯
                backTrack(sb.toString(), usedCount, totalBall, totalList);
                // 4. 弹出
                usedCount -= 3 - existCount;
                itemMap.put(c, itemMap.get(c) + (3 - existCount));
            }
        }
    }

    /**
     * 获取可行的插入位置
     *
     * @param sequences
     * @param c
     * @return
     */
    private List<Integer> getSuitPos(String sequences, Map<Character, Integer> itemMap) {
        List<Integer> positions = new ArrayList<>();
        int flag_idx = 0;
        int count = 0;
        for (int i = 0; i < sequences.length(); i++) {
            char curChar = sequences.charAt(i);
            if (curChar == sequences.charAt(flag_idx)) {
                count++;
                if (i == sequences.length() - 1) {// 到末尾了
                    if (itemMap.containsKey(curChar) && itemMap.get(curChar) + count >= 3) {
                        positions.add(flag_idx);
                    }
                }
            } else {
                if (itemMap.containsKey(sequences.charAt(i - 1)) && itemMap.get(sequences.charAt(i - 1)) + count >= 3) {
                    positions.add(flag_idx);
                }
                flag_idx = i;
                count = 1;
            }
        }
        return positions;
    }

    private String sweep(String sequence) {
        int left = 0, right = 0;
        do {
            if (sequence.charAt(right) == sequence.charAt(left)) {
                if (right == sequence.length() - 1 && right - left >= 2) {// 到最后了
                    sequence = sequence.substring(0, left);
                }
                right++;
            } else {
                if (right - left >= 3) {
                    sequence = sequence.substring(0, left) + sequence.substring(right, sequence.length());
                    left = 0;
                    right = 0;
                    continue;
                } else {
                    left = right;
                    right++;
                }
            }
        } while (left < sequence.length() && right < sequence.length());
        return sequence;
    }


    public static void main(String[] args) {
        int minStep = new P488().findMinStep("RRWWRRBBRR", "WB");
        System.out.println(minStep);
    }

}
